package com.dyz.leetcode._19_greedy;

import java.util.Stack;

public class _402_removeKdigits {
    public String removeKdigits1(String num, int k) {
        StringBuilder sb = new StringBuilder(num);
        for (int i = 0; i < k; i++) {
            boolean hsdelete = false;
            for (int j = 1; j < sb.length(); j++) {

                if(sb.charAt(j)<sb.charAt(j-1)){
                    sb.deleteCharAt(j-1);
                    hsdelete = true;
                    break;
                }
            }
            if(!hsdelete){
                sb.deleteCharAt(sb.length()-1);
            }

        }
        int len = sb.length();

        while (len!=0){
            if(sb.charAt(0)>'0'){
                break;
            }
            sb.deleteCharAt(0);
            len = sb.length();
        }
        return sb.length()==0?"0":sb.toString();
    }

    //贪心+单调栈
    public String removeKdigits(String num, int k) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < num.length(); i++) {
            char c = num.charAt(i);
            while (!stack.isEmpty() && k>0 && stack.peek()>c){
                stack.pop();
                k--;
            }
            stack.push(c);
        }
        for (int i = 0; i < k ; i++) {
            stack.pop();

        }
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()){
            sb.append(stack.pop());
        }
        sb.reverse();
        int len = sb.length();
        while (len!=0){
            if(sb.charAt(0)>'0'){
                break;
            }
            sb.deleteCharAt(0);
            len = sb.length();
        }
        return sb.length()==0?"0":sb.toString();
    }
}
